#ifndef ILLIB_REDBLACKTREE_H_
#define ILLIB_REDBLACKTREE_H_

#include <math.h>
#include <illib/Allocator.h>
#include <illib/BasicRedBlackTree.h>
#include <illib/System.h>
#include <new>


namespace illib {
	namespace RedBlackTree {
		template <typename T> class Tree;
		template <typename T> class Iterator;
		template <typename T> class Functions;
		template <typename T> class Node : public BasicRedBlackTree::Node, public T {
		public:
			typedef Node<T> NodeType;
			typedef Iterator<T> IteratorType;
			typedef Functions<T> FunctionsType;
			typedef Tree<T> TreeType;
			typedef T ElementType;
		private:
			Node(const NodeType &other);
		protected:
			friend class Tree<T>;
			friend class Iterator<T>;
		public:
			static NodeType & create(Allocator & allocator, size_t size){
				size_t allocatedSize;
				uint8_t * memory = allocator.allocate(size, allocatedSize);
				if(reinterpret_cast<uintptr_t>(memory) % alignof(T)) throw Exceptions::alignment;
				NodeType & node = *new(memory) NodeType();
				return node;
			}
			void destroy(){
				this->~Node();
				assert(MemoryTracker::tracker().release(this));
			}
			Node() : BasicRedBlackTree::Node()
			{

			}
		};
		template <typename T> class Functions : public BasicRedBlackTree::TreeFunctions  {
		public:
			typedef Node<T> NodeType;
			typedef Iterator<T> IteratorType;
			typedef Functions<T> FunctionsType;
			typedef Tree<T> TreeType;
			typedef T Type;
		public:
			virtual bool greater(BasicRedBlackTree::Node& left, BasicRedBlackTree::Node& right){
				return greater(static_cast<NodeType&>(left), static_cast<NodeType&>(right));
			}
			virtual bool lesser(BasicRedBlackTree::Node& left, BasicRedBlackTree::Node& right){
				return lesser(static_cast<NodeType&>(left), static_cast<NodeType&>(right));
			}
			virtual bool equal(BasicRedBlackTree::Node& left, BasicRedBlackTree::Node& right){
				return equal(static_cast<NodeType&>(left), static_cast<NodeType&>(right));
			}
			virtual bool greater(NodeType& left, NodeType& right) = 0;
			virtual bool lesser(NodeType& left, NodeType& right) = 0;
			virtual bool equal(NodeType& left, NodeType& right) = 0;
		};

		template <typename T> class Iterator : public BasicRedBlackTree::Iterator {
		public:
			typedef Node<T> NodeType;
			typedef Iterator<T> IteratorType;
			typedef Functions<T> FunctionsType;
			typedef Tree<T> TreeType;
			typedef T ElementType;
		private:
			Iterator(const IteratorType &other);
		protected:
			void init();
		public:
			Iterator(NodeType &low, NodeType &high, TreeType &tree, FunctionsType & functions, bool forward=true) :
				 BasicRedBlackTree::Iterator(low, high, tree, functions, forward)
			{

			}
			Iterator(NodeType &node, TreeType &tree, FunctionsType & functions, bool forward=true) :
				BasicRedBlackTree::Iterator(node, tree, functions, forward)
			{

			}
			Iterator(TreeType &tree, FunctionsType & functions, bool forward=true) :
				BasicRedBlackTree::Iterator(tree, functions, forward)
			{

			}
			NodeType * next(){
				return static_cast<NodeType*>(BasicRedBlackTree::Iterator::next());
			}
			NodeType * current(){
				return static_cast<NodeType*>(BasicRedBlackTree::Iterator::current());
			}
		};

		template <typename T> class Tree : public BasicRedBlackTree::Tree  {
		public:
			typedef Node<T> NodeType;
			typedef Iterator<T> IteratorType;
			typedef Functions<T> FunctionsType;
			typedef Tree<T> TreeType;
			typedef T ElementType;
		private:
			Tree(const TreeType &other);
		protected:
			friend class Iterator<T>;
		public:
			Tree() : BasicRedBlackTree::Tree()
			{

			}
			~Tree(){

			}
			static size_t nodesize(){
				return NodeType::size();
			}
			NodeType * remove(NodeType &node){
				return static_cast<NodeType *>(BasicRedBlackTree::Tree::remove(node));
			}
			NodeType * add(NodeType& node, FunctionsType & functions){
				return static_cast<NodeType *>(BasicRedBlackTree::Tree::add(node, functions));
			}
			NodeType * predecessor(NodeType & node){
				return static_cast<NodeType *>(BasicRedBlackTree::Tree::predecessor(node));
			}
			NodeType * successor(NodeType & node){
				return static_cast<NodeType *>(BasicRedBlackTree::Tree::successor(node));
			}
			void clear(Allocator *allocator, FunctionsType &functions){
				IteratorType i(*this, functions);
				while(i.current()){
					NodeType * node = i.current();
					i.next();
					remove(*node);
					MemoryTracker::Tracked * entry = MemoryTracker::tracker().entry(node);
					node->~NodeType();
					if(!entry) continue;
					Allocator * root = entry->allocator()->root();
					if(!root) continue;
					if(allocator == 0 || root == allocator) assert(entry->allocator()->release(node));
				}
			}
			void clear(){
				BasicRedBlackTree::Tree::clear();
			}

			bool lesser(NodeType& left, NodeType& right, FunctionsType & functions){
				return BasicRedBlackTree::Tree::lesser(left, right, functions);
			}
			bool greater(NodeType& left, NodeType& right, FunctionsType & functions){
				return BasicRedBlackTree::Tree::greater(left, right, functions);
			}
			bool greaterOrEqual(NodeType& left, NodeType& right, FunctionsType & functions){
				return BasicRedBlackTree::Tree::greaterOrEqual(left, right, functions);
			}
			bool lesserOrEqual(NodeType& left, NodeType& right, FunctionsType & functions){
				return BasicRedBlackTree::Tree::lesserOrEqual(left, right, functions);
			}
			bool equal(NodeType& left, NodeType& right, FunctionsType & functions){
				return BasicRedBlackTree::Tree::equal(left, right, functions);
			}
		};
	};
}
#endif /* ILLIB_REDBLACKTREE_H_ */
